/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH25/FONT#8=FIX25



␈↓ α∧␈↓CS206 ␈↓ ∧4COMPUTING WITH SYMBOLIC EXPRESSIONS ␈↓ 
lFALL 1976 


␈↓ α∧␈↓␈↓ ε5MIDTERM

␈↓ α∧␈↓␈↓ ¬i(Open books and notes)

␈↓ α∧␈↓␈↓ αTWrite␈αLISP␈αfunctions␈α
as␈αfollows␈αusing␈α
either␈αexternal␈αor␈α
internal␈αnotation␈αaccording␈αto␈α
your
␈↓ α∧␈↓preference.

␈↓ α∧␈↓1.␈↓ αD(a) ␈↓↓element1[u,n]␈↓ is the ␈↓↓n␈↓th element of the list ␈↓↓u␈↓ and ERROR if there is no such element.

␈↓ α∧␈↓␈↓ αT(b)␈α
␈↓↓element2[x,s]␈↓␈α
is␈α
the␈αsubexpression␈α
at␈α
position␈α
␈↓↓s␈↓␈αin␈α
the␈α
S-expression␈α
␈↓↓x␈↓,␈αwhere␈α
␈↓↓s␈↓␈α
is␈α
a␈αlist␈α
of
␈↓ α∧␈↓whose␈α∞elements␈α
are␈α∞A␈α∞or␈α
D␈α∞and␈α
the␈α∞position␈α∞is␈α
determined␈α∞by␈α
taking␈α∞␈↓αa␈↓␈α∞and␈α
␈↓αd␈↓␈α∞according␈α∞to␈α
the
␈↓ α∧␈↓elements␈α∞of␈α∞␈↓↓s␈↓.␈α∞ Thus␈α∞␈↓↓element2[␈↓(PLUS␈α∞(TIMES␈α∞X␈α∞Y)␈α∞X),␈α∞(D␈α∞A␈α∞D␈α∞D)]␈α∞=␈α∞(Y).␈α∞ The␈α∞value␈α∞of␈α∞the
␈↓ α∧␈↓function is ERROR if there is no such element.

␈↓ α∧␈↓2.␈↓ αD(a) ␈↓↓selectatoms1 u␈↓ is a list of the atoms of the list ␈↓↓u␈↓.

␈↓ α∧␈↓␈↓ αT(b) ␈↓↓selectatoms2 x␈↓ is a list without repetitions of the atoms of the S-expression ␈↓↓x␈↓.

␈↓ α∧␈↓␈↓ αT(c) ␈↓↓select1[p,u]␈↓ is a list of the elements of the list ␈↓↓u␈↓ that satisfy the predicate ␈↓↓p␈↓.

␈↓ α∧␈↓␈↓ αT(d)␈α
␈↓↓select2[p,x]␈↓␈α
is␈α
a␈α
list␈α
of␈α
the␈α
subexpressions␈α
of␈α
the␈α
S-expression␈α
␈↓↓x␈↓␈α
that␈α
satisfy␈α
the␈α
predicate
␈↓ α∧␈↓␈↓↓p␈↓.

␈↓ α∧␈↓␈↓ αT(e)␈α∞␈↓↓select3[p,x]␈↓␈α∞is␈α∞a␈α∞list␈α∞of␈α∞the␈α∂positions␈α∞of␈α∞the␈α∞subexpressions␈α∞of␈α∞the␈α∞S-expression␈α∂␈↓↓x␈↓␈α∞that
␈↓ α∧␈↓satisfy the predicate ␈↓↓p␈↓.  Use the notation for positions described in problem 1.

␈↓ α∧␈↓3. Suppose ␈↓↓successors x␈↓ gives a list of the successor nodes of the node ␈↓↓x␈↓ in some graph.

␈↓ α∧␈↓␈↓ αT(a) ␈↓↓find[x,p]␈↓ is a node satisfying the predicate ␈↓↓p␈↓.

␈↓ α∧␈↓␈↓ αT(b) ␈↓↓findall[x,p]␈↓ is a list of all nodes satisfying the predicate ␈↓↓p␈↓.

␈↓ α∧␈↓4.␈α
A␈α
"program"␈α
in␈α
the␈α
language␈α␈↓↓L␈↓␈α
is␈α
a␈α
list␈α
of␈α
statements␈α
and␈αlabels␈α
where␈α
a␈α
label␈α
is␈α
an␈αatom.␈α
 Each
␈↓ α∧␈↓statement␈α
has␈αone␈α
of␈α
three␈αforms␈α
(GO␈α<label>),␈α
(IF␈α
<anything>␈α<label>)␈α
or␈α<a␈α
list␈α
not␈αbeginning
␈↓ α∧␈↓with␈α
IF␈α
or␈α
GO>.␈α
 A␈α
"program"␈α
π␈α
satisfies␈α
the␈α
predicate␈α
␈↓↓ok[π]␈↓␈α
if␈α
no␈α
label␈α
occurs␈α
more␈α
than␈α
once
␈↓ α∧␈↓and␈α
every␈α
label␈α
occurring␈α
in␈α∞a␈α
GO␈α
or␈α
IF␈α
statement␈α∞occurs␈α
in␈α
the␈α
program.␈α
 Write␈α∞the␈α
predicate
␈↓ α∧␈↓␈↓↓ok[π]␈↓.









␈↓ α∧␈↓␈↓ ε|1␈↓ ∧